package cn.rocky.zuosheng;

import java.util.Stack;

/**
 * @author rocky
 * 1.递归方法 就是利用函数栈 来保存信息
 * 2.用自己申请的数据结构来替代函数栈,也可以实现相同的功能
 */
public class CodeTree {

    public static class Node {
        /**
         * 值
         */
        public int value;
        /**
         * 左节点
         */
        public Node left;

        /**
         * 右节点
         */
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 前序(先序)遍历
     *
     * @param head 头节点
     */
    public void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.println(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    /**
     * 中序遍历
     *
     * @param head 头节点
     */
    public void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value + " ");
        inOrderRecur(head.right);
    }

    /**
     * 后序遍历
     *
     * @param head 头节点
     */
    public void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.value + " ");
    }

    /* ------------------------------------------------- */

    /**
     * 前序(先序)遍历  非递归
     *
     * @param head 头节点
     */
    public void preOrderUnRecur(Node head) {
        System.out.println("pre-order: ");
        if (head != null) {
            // 1.申请一个新的栈,记为stack。然后将头节点head压入stack
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            // 3.不断重复步骤2,直到stack为空,全部过程结束。
            while (!stack.isEmpty()) {
                // 2.从stack中弹出栈顶节点,记为cur,然后打印cur节点的值,再将节点cur的右孩子节点(不为空的话) 先压入stack中,最后将cur 的左孩子节点(不为空的话) 压入stack中
                head = stack.pop();
                System.out.println(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历 非递归
     *
     * @param head 头节点
     */
    public void inOrderUnRecur(Node head) {
        System.out.println("in-order: ");
        if (head != null) {
            // 1.申请一个新的栈,记为stack。初始时,令变量cur=head
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            // 4.当stack为空且head为空,整个过程停止。
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    // 2.先把cur节点压入栈中,对以cur节点为头节点的整棵子树来说,依次把左边界压入栈中,然后重复
                    stack.push(head.left);
                    head = head.left;
                } else {
                    // 3.重复2步骤节点为空,此时从stack中弹出一个节点,打印该值,并且让cur = node.right,重复步骤2
                    head = stack.pop();
                    System.out.println(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    /**
     * 后序遍历 非递归 左右根
     *
     * @param head 头节点
     */
    public void posOrderUnRecur1(Node head) {
        System.out.println("pos-order");
        if (head != null) {
            // 1.申请一个栈,记为stack1,然后将头节点head压入stack1中
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(head);
            while (!stack1.isEmpty()) {
                head = stack1.pop();
                stack2.push(head);
                if (head.left != null) {
                    stack1.push(head.left);
                }
                if (head.right != null) {
                    stack1.push(head.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.println(stack2.pop().value + " ");
            }
        }
        System.out.println();
    }

    /**
     * 后序遍历 非递归 左右根
     *
     * @param head 头节点
     */
    public void posOrderUnRecur2(Node head) {
        System.out.println("pos-order");
        if (head != null) {
            // 1.申请一个栈,记为stack,然后将头节点head压入stack中
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            // 初始时,head为节点1 peek为空
            Node peek = null;
            while (!stack.isEmpty()) {
                // 2.令c等于stack的栈顶节点--节点1,命中第一个if
                peek = stack.peek();
                if (peek.left != null && head != peek.left && head != peek.right) {
                    // 3.将节点压入
                    stack.push(peek.left);
                } else if (peek.right != null && head != peek.right) {
                    stack.push(peek.right);
                } else {
                    System.out.println(stack.pop().value + " ");
                    head = peek;
                }
            }
        }
        System.out.println();
    }

    /**
     * mirrors 通用
     *
     * @param head
     */
    public void morris(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            // 如果当前cur有左子树
            if (mostRight != null) {
                // 找到cur左子树上最右的节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    // 回到最外层的while,继续判断cur的情况
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }

    /**
     * mirrors 前序
     *
     * @param head
     */
    public void morrisPre(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            // 如果当前cur有左子树
            if (mostRight != null) {
                // 找到cur左子树上最右的节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    System.out.println(cur.value + " ");
                    cur = cur.left;
                    // 回到最外层的while,继续判断cur的情况
                    continue;
                } else {
                    mostRight.right = null;
                }
            } else {
                System.out.println(cur.value + " ");
            }
            cur = cur.right;
        }
    }

    /**
     * mirrors 通用
     *
     * @param head
     */
    public void morrisI(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            // 如果当前cur有左子树
            if (mostRight != null) {
                // 找到cur左子树上最右的节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    // 回到最外层的while,继续判断cur的情况
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            System.out.println(cur.value + " ");
            cur = cur.right;
        }
    }

    /**
     * mirrors 后序
     *
     * @param head
     */
    public void morrisPos(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            // 如果当前cur有左子树
            if (mostRight != null) {
                // 找到cur左子树上最右的节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    // 回到最外层的while,继续判断cur的情况
                    continue;
                } else {
                    mostRight.right = null;
                    printEdge(cur.left);
                }
            }
            cur = cur.right;
        }
        printEdge(head);
        System.out.println();
    }

    private static void printEdge(Node head) {
        Node tail = reverseEdge(head);
        Node cur = tail;
        while (cur != null) {
            System.out.println(cur.value + " ");
            cur = cur.right;
        }
        reverseEdge(tail);
    }

    public static Node reverseEdge(Node form) {
        Node pre = null;
        Node next = null;
        while (form != null) {
            next = form.right;
            form.right = pre;
            pre = form;
            form = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.left = new Node(6);
        node.right.right = new Node(7);
        CodeTree codeTree = new CodeTree();
        codeTree.morrisPre(node);
    }
}
